package com.lee.interview.sort;

import java.util.Random;


public class SortUtil {
	
	public static final int SIZE = 10;
	
	public static void main(String[] args) {
		
		int[] intArr = SortUtil.geneateInArray(SIZE);
		SortUtil.printArray(intArr);
//		SortTest.bubbleSort(intArr);
//		SortUtil.selectionSort(intArr);
//		SortUtil.insertionSort(intArr);
		SortUtil.quickSort(intArr, 0, intArr.length-1);
		SortUtil.printArray(intArr);
		
	}
	
	public static int[] geneateInArray(int size) {
		int[] intArr = new int[size];
		Random random = new Random();
		for (int i = 0; i < intArr.length; i++) {
			intArr[i] = random.nextInt(size*10);
		}
		return intArr;
	}
	
	public static void printArray(int[] intArr) {
		for (int i = 0; i < intArr.length; i++) {
			System.out.print(intArr[i]+"	");
		}
		System.out.println();
	}

	public static int[] bubbleSort(int[] sortArr) {
		for (int i = 0; i < sortArr.length-1; i++) {
			for (int j = 0; j < sortArr.length-1-i; j++) {
				if (sortArr[j]>sortArr[j+1]) {
					int temp = sortArr[j];
					sortArr[j] = sortArr[j+1];
					sortArr[j+1] = temp;
				}
			}
		}
		return sortArr;
	}
	
	public static int[] selectionSort(int[] intArr) {
		for (int i = 0; i < intArr.length-1; i++) {
			int minValueIndex = i;
			for (int j = i+1; j < intArr.length; j++) {
				if (intArr[minValueIndex]>intArr[j]) {
					minValueIndex = j;
				}
			}
			if (minValueIndex!=i) {
				int temp = intArr[i];
				intArr[i] = intArr[minValueIndex];
				intArr[minValueIndex] = temp;
			} 
		}
		return intArr;
	}
	
	public static int[] insertionSort(int[] intArr) {
		for (int i = 1; i < intArr.length; i++) {
			int currValue = intArr[i];
			int j = i;
			while (j>0 && currValue < intArr[j-1]) {
				intArr[j] = intArr[j-1];
				j--;
			}
			intArr[j] = currValue;
		}
		return intArr;
	}
	
	public static int[] quickSort(int[] intArr,int low,int high) {
		int left = low;
		int right = high;
		if (left < right) {
			int pivotValue = intArr[left];
			while (left < right) {
				// 从右往左查找，找到小于pivotValue的数据
				while(left < right && pivotValue < intArr[right]) {
					right--;
				}
				if (left < right) {
					// 右边存在小于pivotValue的值
					intArr[left] = intArr[right];
					left++;
				}
				//从左往右查询，找到大于pivotValue的数
				while (left<right && pivotValue > intArr[left]) {
					left++;
				}
				if (left<right) {
					intArr[right] = intArr[left];
					right--;
				}
			}
			// while循环结束，进行下一次迭代
			intArr[left] = pivotValue;
			quickSort(intArr, low, left-1);
			quickSort(intArr, left+1, high);
		}

		return intArr;
	}
	
	
}
